package JZ55_链表中环的入口结点;


class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null){
            return null;
        }
        // 1.判断链表中有环
        ListNode l = pHead;
        ListNode f = pHead;
        boolean flag = false;
        while (f != null && l != null && f.next != null){
            l = l.next;
            f = f.next.next;

            if (l == f){
                flag = true;
                break;
            }
        }

        if (!flag){
            return null;
        }else {
            // 2.得到环中结点的数目
            int n = 1;
            f = f.next;
            while (l != f){
                f = f.next;
                n++;
            }

            // 3.找到环中的入口结点
            l = f = pHead;
            for (int i = 0; i < n; i++){
                f = f.next;
            }
            while (l != f){
                l = l.next;
                f = f.next;
            }
            return f;
        }
    }
}